Search results for "Column generation"
showing 10 items of 15 documents
Contributions to Branch-and-Price-and-Cut Algorithms for Routing Problems
2019
This article deals with new exact branch-and-price-and-cut algorithms for the solution of routing problems. Specialized methods for the pickup-and-delivery problem (PDP), the truck-and-trailer routing problem (TTRP), the periodic vehicle routing problem (PVRP) and a service network design and hub location problem (SNDHLP) are presented. We develop a new technique for the acceleration of bidirectional labeling algorithms by a dynamic choice of the merge point. Moreover, for variants of the PDP, the bidirectional labeling can be effectively applied for the first time. In the TTRP, we model the extension to a 2 days planning horizon and the consideration of a quantity-dependent transfer time. …
Branch-price-and-cut algorithms for the pickup and delivery problem with time windows and multiple stacks
2016
Abstract This paper proposes models and algorithms for the pickup and delivery vehicle routing problem with time windows and multiple stacks. Each stack is rear-loaded and is operated in a last-in-first-out (LIFO) fashion, meaning that when an item is picked up, it is positioned at the rear of a stack. An item can only be delivered if it is in that position. This problem arises in the transportation of heavy or dangerous material where unnecessary handling should be avoided, such as in the transportation of cars between car dealers and the transportation of livestock from farms to slaughterhouses. To solve this problem, we propose two different branch-price-and-cut algorithms. The first sol…
Stabilized branch-price-and-cut for the commodity-constrained split delivery vehicle routing problem
2019
Abstract In the commodity-constrained split delivery vehicle routing problem (C-SDVRP), customer demands are composed of sets of different commodities. The C-SDVRP asks for a minimum-distance set of routes such that all customer demands are met and vehicle capacities are respected. Moreover, whenever a commodity is delivered by a vehicle to a customer, the entire amount requested by this customer must be provided. Different commodities demanded by one customer, however, can be delivered by different vehicles. Thus, the C-SDVRP is a relaxation of the capacitated vehicle routing problem and a restriction of the split delivery vehicle routing problem. For its exact solution, we propose a branc…
A Branch-Price-and-Cut Algorithm for the Min-Max k -Vehicle Windy Rural Postman Problem
2013
[EN] The min-max k -vehicles windy rural postman problem consists of minimizing the maximal distance traveled by a vehicle to find a set of balanced routes that jointly service all the required edges in a windy graph. This is a very difficult problem, for which a branch-and-cut algorithm has already been proposed, providing good results when the number of vehicles is small. In this article, we present a branch-price-and-cut method capable of obtaining optimal solutions for this problem when the number of vehicles is larger for the same set of required edges. Extensive computational results on instances from the literature are presented.
A computational study of LP-based heuristic algorithms for two-dimensional guillotine cutting stock problems
2002
In this paper we develop and compare several heuristic methods for solving the general two-dimensional cutting stock problem. We follow the Gilmore-Gomory column generation scheme in which at each iteration a new cutting pattern is obtained as the solution of a subproblem on one stock sheet. For solving this subproblem, in addition to classical dynamic programming, we have developed three heuristic procedures of increasing complexity, based on GRASP and Tabu Search techniques, producing solutions differing in quality and in time requirements. In order to obtain integer solutions from the fractional solutions of the Gilmore-Gomory process, we compare three rounding procedures, rounding up, t…
In-Depth Analysis of Pricing Problem Relaxations for the Capacitated Arc-Routing Problem
2015
Recently, Bode and Irnich [Bode C, Irnich S (2012) Cut-first branch-and-price-second for the capacitated arc-routing problem. Oper. Res. 60(5):1167–1182] presented a cut-first branch-and-price-second algorithm for solving the capacitated arc-routing problem (CARP). The fundamental difference to other approaches for exactly solving the CARP is that the entire algorithm works directly on the typically sparse underlying graph representing the street network. This enables the use of highly efficient dynamic programming-based pricing algorithms to solve the column-generation subproblem also known as the pricing problem. The contribution of this paper is the in-depth analysis of the CARP pricing…
Effective Handling of Dynamic Time Windows and Its Application to Solving the Dial-a-Ride Problem
2015
A dynamic time window relates to two operations that must be executed within a given time meaning that the difference between the points in time when the two operations are performed is bounded from above. The most prevalent context of dynamic time windows is when precedence is given for the two operations so that it is a priori specified that one operation must take place before the other. A prominent vehicle routing problem with dynamic time windows and precedence is the dial-a-ride problem (DARP), where user-specified transportation requests from origin to destination points must be serviced. The paper presents a new branch-and-cut-and-price solution approach for the DARP, the prototypi…
The shortest-path problem with resource constraints with -loop elimination and its application to the capacitated arc-routing problem
2014
Abstract In many branch-and-price algorithms, the column generation subproblem consists of computing feasible constrained paths. In the capacitated arc-routing problem (CARP), elementarity constraints concerning the edges to be serviced and additional constraints resulting from the branch-and-bound process together impose two types of loop-elimination constraints. To fulfill the former constraints, it is common practice to rely on a relaxation where loops are allowed. In a k-loop elimination approach all loops of length k and smaller are forbidden. Following Bode and Irnich (2012) for solving the CARP, branching on followers and non-followers is the only known approach to guarantee integer …
Bidirectional labeling in column-generation algorithms for pickup-and-delivery problems
2018
Abstract For the exact solution of many types of vehicle-routing problems, column-generation based algorithms have become predominant. The column-generation subproblems are then variants of the shortest-path problem with resource constraints which can be solved well with dynamic-programming labeling algorithms. For vehicle-routing problems with a pickup-and-delivery structure, the strongest known dominance between two labels requires the delivery triangle inequality (DTI) for reduced costs to hold. When the direction of labeling is altered from forward labeling to backward labeling, the DTI requirement becomes the pickup triangle inequality (PTI). DTI and PTI cannot be guaranteed at the sam…
A new branch-and-price algorithm for the traveling tournament problem
2010
Abstract The traveling tournament problem ( ttp ) consists of finding a distance-minimal double round-robin tournament where the number of consecutive breaks is bounded. For solving the problem exactly, we propose a new branch-and-price approach. The starting point is a new compact formulation for the ttp . The corresponding extensive formulation resulting from a Dantzig-Wolfe decomposition is identical to one given by Easton, K., Nemhauser, G., Trick, M., 2003. Solving the traveling tournament problem: a combined interger programming and constraint programming approach. In: Burke, E., De Causmaecker, P. (Eds.), Practice and Theory of Automated Timetabling IV, Volume 2740 of Lecture Notes i…